package com.itheima.suanfa;

import java.util.Arrays;

/*
快排
 */
public class Demo03 {


    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
//        调用快排方法对数组 进行排序
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    //定义快排方法  内部完成 排序操作
    public static void quickSort(int[] arr, int left ,int  right){
        if(left>right){
            return;
        }
        int  left0=left;
        int right0=right;
        int  jizhun=arr[left0];
        while (left!=right) {//不断的寻找知道找到基准数的位置
            //从右边找比基准数小的
            while (arr[right]>=jizhun&&left<right){
                right--;
            }
            //从左边找比基准数 大的
            while (arr[left]<=jizhun&&left<right){
                left++;
            }
            //左边和右边交换
            int temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
        }
        //基准数归位
        int temp=arr[left0];
        arr[left0]=arr[left];
        arr[left]=temp;

        //左边 往左边递归
        quickSort(arr,left0,left-1);

        //右边往 右边递归
        quickSort(arr,left+1,right0);


    }




}
